package ru.susu.algebra.partition;

import java.util.Arrays;

/**
 * @author akargapolov
 * @since: 01.03.2009
 */
public class PartitionEnumerator
{
	private static int INITIAL_SIZE = 512;// 1001;

	private static Long[][] _dpByEnd = new Long[INITIAL_SIZE][INITIAL_SIZE];

	private static Long[][] _dpByStart = new Long[INITIAL_SIZE][INITIAL_SIZE];

	private static int _size = INITIAL_SIZE;

	static
	{
		initByEndTable();
		initByStartTable();
		checkTables();
	}

	public static Long getPartitionsNumber(int n)
	{
		return _dpByStart[n][1];
	}

	public static Long getNumber(Partition p)
	{
		int sum = p.getPresentedNumber();

		while (sum + 1 > _size)
		{
			increaseTableSize();
		}
		return getNumber(p.getArrayRepresentation(), 0, sum);
	}

	public static Long getNumber(Integer[] array)
	{
		int sum = 0;
		for (int i = 0; i < array.length; i++)
		{
			sum += array[i];
		}

		while (sum + 1 > _size)
		{
			increaseTableSize();
		}
		return getNumber(array, 0, sum);
	}

	private static Long getNumber(Integer[] array, int index, int sum)
	{
		if (index == array.length)
		{
			return Long.valueOf(0);
		}
		int start = index == 0 ? 1 : array[index - 1];
		Long res = _dpByStart[sum][start] - _dpByStart[sum][array[index]];
		res += getNumber(array, index + 1, sum - array[index]);
		return res;
	}

	/*
	 * private static Long getNumber(Integer[] array, int index, int sum) { if
	 * (index == array.length) { return Long.valueOf(0); } Long res =
	 * Long.valueOf(0); res += _dpByEnd[sum][array[index] - 1] +
	 * getNumber(array, index + 1, sum - array[index]); return res; }
	 */

	private static void increaseTableSize()
	{
		_size = _size << 1;
		_dpByEnd = new Long[_size][_size];
		_dpByStart = new Long[_size][_size];
		initByEndTable();
		initByStartTable();
		checkTables();
	}

	private static void initByEndTable()
	{
		int i, j;
		Arrays.fill(_dpByEnd[0], Long.valueOf(0));
		for (i = 1; i < _size; i++)
		{
			_dpByEnd[i][0] = Long.valueOf(0);
			for (j = 1; j < _size; j++)
			{
				_dpByEnd[i][j] = _dpByEnd[i][j - 1];
				if (i >= j)
				{
					_dpByEnd[i][j] += _dpByEnd[i - j][j];
				}
				if (i == j)
				{
					_dpByEnd[i][j]++;
				}
			}
		}
	}

	private static void checkTables()
	{
		for (int i = 1; i < _size; i++)
		{
			if (!_dpByEnd[i][i].equals(_dpByStart[i][1]))
			{
				System.out.print(_dpByEnd[i][i] + "_" + _dpByStart[i][1] + "\n");
			}
		}
	}

	private static void initByStartTable()
	{
		int i, j;
		for (i = 0; i < _size; i++)
		{
			Arrays.fill(_dpByStart[i], Long.valueOf(0));
			_dpByStart[i][i] = Long.valueOf(1);
			for (j = i - 1; j >= 1; j--)
			{
				_dpByStart[i][j] = _dpByStart[i][j + 1] + _dpByStart[i - j][j];
			}
		}
	}

	public static Integer[] getArray(long order, int sum)
	{
		while (sum + 1 > _size)
		{
			increaseTableSize();
		}
		Integer[] array = new Integer[sum];
		Arrays.fill(array, -1);
		int length = fillArray(order, 1, sum, array, 0);
		return Arrays.copyOf(array, length);
	}

	private static int fillArray(long order, int cur, int sum, Integer[] array, int index)
	{
		if (sum == 0)
		{
			return 0;
		}
		long different = _dpByStart[sum][cur] - _dpByStart[sum][cur + 1];
		if (order < different)
		{
			array[index] = cur;
			return fillArray(order, cur, sum - cur, array, index + 1) + 1;
		}
		else
		{
			return fillArray(order - different, cur + 1, sum, array, index);
		}
	}

}
